There are many commercially successful non-volatile memory products being used today, particularly in the form of small form factor cards, which employ flash EEPROM (Electrically Erasable and Programmable Read Only Memory) cells formed on one or more integrated circuit devices. Some of the commercially available card formats include CompactFlash (CF) cards, MultiMedia cards (MMC), Secure Digital (SD) cards, and personnel tags (P-Tag). Hosts that may incorporate or access non-volatile small form factor cards include personal computers, notebook computers, personal digital assistants (PDAs), various data communication devices, digital cameras, cellular telephones, portable audio players, automobile sound systems, and similar types of equipment. Control of the memory may be achieved by software on a controller in the card. Besides a memory card implementation, this type of memory can alternatively be embedded into various types of host systems. In both removable and embedded applications, host data may be stored in the memory according to a storage scheme implemented by memory controller software and/or hardware. The data stored within a card is accessed via an interface that is controlled by a program and, in some cases, security hardware or software.
The increase in storage density of non-volatile memory cards allows an ever-growing number of host applications to make use of the additional storage space. For example, the additional space may be utilized for storage of MP3 audio files, high-resolution images files, video files, and documents. In cellular telephone applications, the non-volatile storage space may store a variety of data for advanced cellular telephone services, such as storing Multimedia Messaging Service (MMS) object attachments. The storage space may also facilitate full personal information management (PIM) functionality by allowing the storage of e-mail contact lists and calendars. The files may be organized in the card according to a file system stored on the card and at least partially maintained by the host accessing the card.
Certain file system operations, such as writing a file to a non-volatile storage device or memory card, can be thought of as transitioning the device from one consistent data state to another consistent data state. A sequence of separate transactions between the storage device and the host device may be required in order to cause the transition between consistent data states. A loss of power to the card (possibly caused by removing the card, or because of a loss of power to the host device) in the middle of this sequence of transactions may easily destroy the consistency of the file system.
For example, the host may direct the host device driver to overwrite a block of data in a non-volatile storage device. The process of overwriting a block in a non-volatile storage device with new data may not be atomic. The term atomicity refers to an operation that is guaranteed to proceed to completion or have no effect at all.
An atomic transaction refers to a set of operations that, from the perspective of the host caller, appears as a single operation that either succeeds or fails to execute. Overwriting a block may not be atomic because a host device driver may need to issue several separate commands to the non-volatile storage device in order to complete this operation. If a power loss occurs during the middle of the sequence of commands, the block may be left half written, with part of the block containing old data and part of the block containing new data. Consistent data states include the block with fully old data (before any overwriting occurs), or the block once fully overwritten with new data. However, when the block contains a mixture of old and new data, it is in an inconsistent data state, as it leaves the storage device or card file system in a state which is not the old state (before the write operation) or the new one (after a successful write operation).
In another example, a host application may issue a command to the file system to write a new file to the non-volatile storage device. To complete this task, the file system may issue a sequence of several device driver commands. It is possible that a power loss within the sequence of commands will allow only a few of them to be completed, while others will not take place. For example, the file might actually be written into the device, but its directory entry may not be written, so that it might now be impossible to locate the file. A more severe danger occurs when overwriting an existing file with new contents, where it might happen that the previous contents are already lost while the new contents have not yet been written—a situation which is highly undesirable. An even more severe danger occurs when the integrity of the file system structures themselves are damaged by interrupting a sequence of non-atomic operations, as the whole device contents may be lost if the file system is not designed to accommodate a power loss scenario during the update of a file allocation table.
Different techniques exist for handling a power loss scenario by providing a “ruggedized” file system for the non-volatile storage device. A ruggedized file system has the capability of staying in or being recovered to a certain known consistent data state until a sequence of operations is completed and a new known consistent data state is reached. Any interruption (such as a sudden power-loss) before reaching the new consistent data state will cause a “roll-back” of the operations which occurred after the previous consistent data state, leaving the component in this first state. In other words, a sequence of file system operations may end in a new consistent data state or in a previous consistent data state, but never in between. Thus, a ruggedized file system can survive any sudden power loss without losing its consistency, and can be recovered to a consistent data state.
Some techniques to ruggedize a file system have involved periodically copying all or a portion of the file system to another media such as a backup tape. If a failure occurs, the file system can be retrieved from the backup copy to recover a consistent data state. This method usually requires manual intervention and/or bringing the whole storage system offline when making the backup or restoring from it. Another technique implemented by some file systems does not backup the whole device contents but rather only the metadata of the file system. The backup data copy is stored on the protected device. Yet another technique involves duplicating only a portion of the file system metadata in order to create a backup for ruggedization purposes, thus reducing the performance and storage penalty associated with creating the backup.
These methods for achieving file system ruggedness are based on implementing special data structures and algorithms at the file system level. For example, these prior methods require the implementation of special snapshot bits for each block entry in the file system allocation table, and also require changing how file deletion works, to avoid erasing blocks that may still be needed for a previous snapshot of the file system. Using special data structures and algorithms at the file system level has several disadvantages. First, if the ruggedized file system is a specially designed one, with unique algorithms and data structures, utilizing another file system more suitable for a particular application requires giving up the ruggedized features, or porting the ruggedized features to the other file system. Second, a ruggedized file system using special data structures may be incompatible with other file systems. If a storage device is moved from a system with a ruggedized file system into a system with a non-ruggedized file system or vice versa, the device contents might be interpreted differently or may even not be readable at all. Third, if ruggedized file systems typically employ special algorithms all the time, a storage space and performance penalty is incurred even when some operations to the non-volatile storage device do not require ruggedness protection.
Another known technique for addressing file system ruggedness includes providing the ruggedness feature to the non-volatile storage device not inside the file system itself, but rather, in the block device driver servicing file system commands. In order to provide ruggedness features, the block device driver exports commands that allow the file system to define the current state of the non-volatile storage device as a consistent data state, and mark the beginning and end of a sequence of commands that may be required in order to cause the transition between consistent data states. In doing so, the block device driver may perform a sequence to recover a consistent data state in the event of a power loss. This technique involves modification to the block device driver of the host in communication with a non-volatile storage device, as the block device driver maintains the requisite data structures to provide ruggedness and recover the non-volatile storage device to a consistent data state in the event of a power loss. Further, if a power loss event occurs because the non-volatile storage device is removed from one host during a transition between consistent data states, and the non-volatile storage device is subsequently reconnected to another host without a ruggedized block device driver, recovery of a consistent data state in the non-volatile storage device may not be possible.